Mong-Jen Kao (高孟駿)

x

Research Interests

Design and Analysis of Approximation Algorithms,
Computational Complexity Theory

Quantum Computing,
Cryptography and Security

Recruiting Message / 招募訊息

I am recruiting self-motivated PhD/MS/BS students for research works.
Students who are willing to work spontaneously on theory problems are welcome to contact me.

In addition to theory research works, I plan to recruit one MS student for implementation-oriented works regarding the NYCU-OJ Project.
Contact me if you're interested.
除了演算法工作以外, 我計畫招募 1 名實作導向的碩士生, 協助 NYCU-OJ Project 的開發.
有興趣的同學, 請 email 與我聯絡洽談.

x

Honor / Awards

Humboldt Research Fellowship for Experienced Researchers,
Alexander von Humboldt-Stfiftung.
德國宏博基金會 - 宏博資深學者研究獎助, 2024.
Early-Career Investigator Research Achievement Award,
Academia Sinica, 2021.

中央研究院 - 2021「年輕學者研究成果獎」
Young Scholar Innovation Award,
Foundation for the Advancement of Outstanding Scholarship (FAOS), 2022.
傑出人才發展基金會 - 第十屆「年輕學者創新獎」
NSTC Excellent Young Scholar Award, 2023 & 2024.
國家科學及技術委員會優秀年輕學者研究計畫 - 2023, 2024.
AACT Best Journal Paper Award, 2015, 2019, 2021, 2022.
演算法與計算理論學會 - 「最佳期刊論文獎」

Work Experience

2021 - present, Associate Professor, Department of CS, National Yang-Ming Chiao-Tung University, Hsincu, Taiwan.
2018 - 2021, Assistant Professor, Department of CSIE, National Chung-Cheng University, Chiayi, Taiwan.
2012 - 2018, Postdoc, IIS, Academia Sinica, Taipei, Taiwan.

Education

Ph.D, Department of CSIE, National Taiwan University, 2012.
M.S., Department of CSIE, National Taiwan University, 2008.
B.S., CS (Major) and Math (Minor), National Taiwan University, 2006.
National Chang-Hua Senior High School, 2001.

Funded Research Projects

2024 - 2027, "Approximation Algorithms for Hard Capacitated Problems, Precedence-Constrained Scheduling, and Related Issues (II)",
funded under the NSTC Excellent Young Scholar Award.
2023 - 2026, "Algorithmic Study on Subgraph Covering, Capacitated Covering, and Related Route Planning Problems",
funded under the NSTC Excellent Young Scholar Award.
(co-PI) 2024 - 2025, "次世代行動網路安全技術與基礎研究(2/2)", 國科會資安策略專案計畫.
(co-PI) 2023 - 2027, "基於微服務的智慧軟體開發與教學平台(2/4)", 教育部智慧創新關鍵人才躍升計畫(ITSA) - 跨域軟體服務實踐人才培育示範團隊計畫.

Past Projects:

(co-PI) 2023 - 2024, "次世代行動網路安全技術與基礎研究(1/2)", 國科會資安策略專案計畫.
2022 - 2024, "Approximation Algorithms for Hard Capacitated Problems, Precedence-Constrained Scheduling, and Related Issues", research project funded by MOST.
2019 - 2022, "LP-based Approximations for Scheduling, Clustering, and Related Issues", research project funded by MOST.
2018 - 2021, "Algorithmic Research on Capacitated Covering and Related Problems", research project funded by MOST.
2015 - 2018, "Algorithmic Study on Capacitated Covering and Energy-Efficient Scheduling", Postdoctoral Scholar Program funded by Academia Sinica.
2010 - 2012, "Sandwich Programme" - NSC-DAAD-sponsored Ph.D training program.
2005 - 2006, "Dominating Set and Related Problems," an NSC-sponsored research programme for undergraduate students.

x

Selected Papers

Mong-Jen Kao,
"On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem".
In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'23), January 22-25, 2023, Florence, Italy.

Mong-Jen Kao,
"Iterative Partial Rounding for Vertex Cover with Hard Capacities".
In procedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January 16-19, 2017, Barcelona, Spain. ([arXiv])

Recent Works

Mong-Jen Kao,
"A 4-approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost",
In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

Ting-Yo Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao,
"On Min-Max Graph Balancing with Strict Negative Correlation Constraints",
In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

Shu-Wei Chang, Jian-Jhih Kuo, Mong-Jen Kao, Bo-Zhong Chen, and Qian-Jing Wang,
"Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks",
In the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, 2024, Vancouver, Canada.

Hyung-Chan An and Mong-Jen Kao,
"On the Connected Minimum Sum of Radii Problem",
To appear in the 35th International Symposium on Algorithms and Computation (ISAAC 2024), December 8-11, Sydney, Australia.

Journal Articles

Eunpyeong Hong and Mong-Jen Kao,
"Approximation Algorithm for Vertex Cover with Multiple Covering Constraints". Algorithmica, 84: 1-12, 2022. DOI: 10.1007/s00453-021-00885-w

Mong-Jen Kao,
"Iterative Partial Rounding for Vertex Cover with Hard Capacities". Algorithmica, 83(1): 45-71, 2021. DOI: 10.1007/s00453-020-00749-9

Mong-Jen Kao, Jia-Yau Shiau, Ching-Chi Lin, and D.T. Lee,
"Tight Approximation for Partial Vertex Cover with Hard Capacities". Theoretical Computer Science, 778: 61-72, 2019. DOI: 10.1016/j.tcs.2019.01.027

Mong-Jen Kao, Hai-Lun Tu, and D.T. Lee,
"O(f) Bi-approximation for Capacitated Covering with Hard Capacities". Algorithmica, 81(5): 1800-1817, 2019. DOI: 10.1007/s00453-018-0506-6
Bang-Sin Dai, Mong-Jen Kao, and D.T. Lee,
"Optimal Time-convex Hull for a Straight-line Highway in Lp-metrics". Computational Geometry, volume 53, page 1-20, 2016.

Mong-Jen Kao, Han-Lin Chen, and D.T. Lee,
"Capacitated Domination: Problem Complexity and Approximation Algorithms". Algorithmica, 72(1): 1-43, 2015.

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner,
"Online Dynamic Power Management with Hard Real-Time Guarantees". Theoretical Computer Science, volume 595, pages 46-64, 2015.

Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, and Dorothea Wagner,
"Density Maximization Problem in Graphs". Journal of Combinatorial Optimization, 26(4): 723-754, 2013.

Mong-Jen Kao, Chung-Shou Liao, and D.T. Lee,
"Capacitated Domination Problem". Algorithmica, 60:274-299, 2011.

International Conference Papers

Hyung-Chan An and Mong-Jen Kao,
"On the Connected Minimum Sum of Radii Problem",
To appear in the 35th International Symposium on Algorithms and Computation (ISAAC 2024), December 8-11, Sydney, Australia.

Shu-Wei Chang, Jian-Jhih Kuo, Mong-Jen Kao, Bo-Zhong Chen, and Qian-Jing Wang,
"Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks",
In the IEEE International Conference on Computer Communications (INFOCOM 2024), May 20-23, Vancouver, Canada.

Mong-Jen Kao,
"A 4-approximation Algorithm for Capacitated Facility Location with Uniform Facility Cost",
In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

Ting-Yo Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao,
"On Min-Max Graph Balancing with Strict Negative Correlation Constraints",
In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), December 3-6, Kyoto, Japan.

Mong-Jen Kao,
"On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem".
In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'23), January 22-25, 2023, Florence, Italy.

Eunpyeong Hong and Mong-Jen Kao,
"Approximation Algorithm for Vertex Cover with Multiple Covering Constraints".
In proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), December 16-19, 2018, Yilan, Taiwan.

Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D.T. Lee,
"Tight Approximation for Partial Vertex Cover with Hard Capacities".
In proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC'17), December 09-12, 2017, Phuket, Thailand.

Mong-Jen Kao,
"Iterative Partial Rounding for Vertex Cover with Hard Capacities".
In procedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'17), January 16-19, 2017, Barcelona, Spain. ([arXiv])

Mong-Jen Kao, Hai-Lun Tu, and D.T. Lee, "O(f) Bi-approximation for Capacitated Covering with Hard Capacities". In proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC'16), December 12-14, 2016, Sydney, Australia. ([arXiv])

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner, "Online Dynamic Power Management with Hard Real-Time Guarantees". In proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS'14), March 5-8, 2014, Lyon, France. ([arXiv])

Bang-Sin Dai, Mong-Jen Kao, and D.T. Lee, "Optimal Time-Convex Hull under the Lp Metrics". In proceedings of the 13rd Algorithms and Data Structures Symposium (WADS'13), August 12-14, London, Canada. ([arXiv])

Mong-Jen Kao, Jian-Jia Chen, Ignaz Rutter, and Dorothea Wagner, "Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem". In proceedings of the 23rd International Symposium on Algorithms and Computatoin (ISAAC'12), December 19-21, Taipei, Taiwan. ([arXiv])

Mong-Jen Kao and D.T. Lee, "Capacitated Domination: Constant Factor Approximations for Planar Graphs". In proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC'11), December 5-8, 2011, Yokohama, Japan.

Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Martin Nöllenburg, Ignaz Rutter, and Dorothea Wagner, "Connecting Two Trees with Optimal Routing Cost". In proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG'11), August 10-12, 2011, Toronto, Canada.

Mong-Jen Kao, Bastian Katz, Marcus Krug, D.T. Lee, Ignaz Rutter, and Dorothea Wagner, "Density Maximization Problem in Graphs". In proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON'11), August 14-16, 2011, Dallas, US.

Mong-Jen Kao and Han-Lin Chen, "Approximation Algorithms for the Capacitated Domination Problem". In proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW'2010), August 11-13, 2010, Wuhan, China. (Best Student Paper Award)

Mong-Jen Kao and Chung-Shou Liao, "Capacitated Domination Problem". In Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC'2007), December 17-19, 2007, Sendai, Japan.

Other Works

Ren-Ce Luo, Mong-Jen Kao, and D.T. Lee, Multi-Core Coherent Speed Scaling to Minimize Energy Consumption. In the 9th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2016), May 14-16, 2016, Taipei, Taiwan.
(Best Presentation Award, conferred to Ren-Ce)

Hung-I Yu, Mong-Jen Kao, and D.T. Lee, "The Multi-Service Location Problems".
In the proceedings of the 2018 International Computer Symposium, Dec 20-22, 2018, Yunlin, Taiwan.

Hai-Lun Tu, Mong-Jen Kao, and D.T. Lee, "An O(f) Bi-Approximation for Weighted Capacitated Covering with Hard Capacities".
In the proceedings of the 2018 International Computer Symposium, Dec 20-22, 2018, Yunlin, Taiwan.

Mong-Jen Kao, D.T. Lee, and Dorothea Wagner,
"Approximating Metrics by Tree Metrics of Small Distance-Weighted Average Stretch", 2013. [arXiv]

Thesis & Dissertation

"An Algorithmic Approach to Local and Global Resource Allocations".
Ph.D Dissertation, National Taiwan University, Taiwan, 2012.

"Capacitated Domination Problem".
Master Thesis, National Taiwan University, Taiwan, 2008. (Master Thesis Award from IICM, Taiwan.)

x

Forthcoming

113-2 Combinatorial Mathematics

Current

113-1 Introduction to Algorithms, Approximation Algorithms, Algorithm and Problem Solving Practice

Past

112 Approximation Algorithms, Combinatorial Mathematics
111 - Approximation Algorithms, Combinatorial Mathematics, Selected Topics in Intractable Problems and Complexity
110 - Approximation Algorithms, Combinatorial Mathematics
109 (in CCU) - Program Design & Quiz (I) (II), Geometric Algorithms
108 (in CCU) - Program Design & Quiz (I) (II), Geometric Algorithms, Graph Algorithms
107 (in CCU) - Program Design & Quiz (I) (II)

x

2024-06-13 期末聚餐 & 導生聚

For Students @ NYCU

各位陽明交大的同學好,

我個人的研究主軸, 圍繞在各類型基礎組合最佳化問題的近似演算法設計分析、以及可近似困難度的研究上面。
過去曾在 Capacitated Covering / Location 等具挑戰性的問題上得到一系列的結果,
並在演算法領域頂尖國際會議 SODA 上發表數篇單一作者研究成果。

除此之外, 近年我也與實驗室的研究生/專題生探討基礎排程問題、route planning、clustering、以及 Distance Embedding 問題等。
這些都是相當有趣、同時也具高度挑戰性的演算法研究問題。

我的實驗室的研究方向, 也圍繞在與演算法相關的主題上,
並有相當亮眼的研究成果(感謝優秀又努力的同學們).

具有代表性的研究成果, 包括以下幾項 (僅列出實驗室同學有參與的部份):

Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks
此項研究探討 IoT 網路中使用無人機蒐集資料所對應到的路徑規劃問題,
實際上對應的是一個 minimum cycle cover 問題.
針對此問題, 我的碩班學生書維應用了 Traveling Salesman Problem (TSP) 問題在幾何空間上的 PTAS 近似演算法的技巧,
並解決其對應的動態規劃 (dynamic programming) 問題以及相關衍生的分析,
在實務的假設下, 成功得到一個 3 倍的近似演算法, 達到實務上 35%~58% 的改進。
此項結果發表在網路與通訊領域的頂尖國際會議 INFOCOM 2024,
此年度台灣僅有兩篇 INFOCOM 論文, 其中一篇由我的碩班學生張書維所貢獻.
On Min-Max Graph Balancing with Strict Negative Correlation Constraints
此項研究探討圖(graph)上的 min-max balancing 問題,
實際上對應的是一個 unrelated scheduling with restricted assignment model.
對此問題, 我的碩班學生庭佑做了一系列完整的複雜度探討,
並針對可解決的case, 使用線性規劃以及 2-SAT 問題的技巧, 提出了兩倍的近似演算法。
此項結果發表於演算法的重要國際會議 ISAAC 2024,
此年度台灣僅有兩篇 ISAAC 國際會議的論文, 兩篇皆由我的實驗室所貢獻.

我個人相信, 傑出的研究成果, 來自於天賦與努力兩者的結合.
因此, 我期望我實驗室的學生, 能夠持續努力且用心地面對本份內的研究工作, 並在碩班期間, 創造佳蹟, 累積未來的競爭力。

我的實驗室正在招募對演算法/理論研究有興趣以及熱忱的專題生/碩博班學生，
若你對演算法/理論相關的題材，有高度的熱忱、也想試著專注做深入的研究、面對挑戰，歡迎與我聯絡。(2024-11-5)

Members

PI - Mong-Jen Kao 高孟駿

MS Students

111 - 林翊婷, The NYCU-OJ project, approx algorithms
112 - 謝翊庭, scheduling problems
112 - 錢明皇, 鄭丞洋, quantum network routing, tour planning
112 - 劉仲昀, scheduling problems
113 - 白宇辰, 陳冠瑄, 陳靖燁

BS Students & PT-RAs

110 - 林伯蔚, 劉金丞, quantum cryptography
111 - 李慕庭, connectivity
111 - 廖修誼, tour planning problem
111 - 林晉湧

Alumni (@NYCU)

張書維, 2022/09 - 2024/06. @ MediaTek
MS Research Work - ``Near-Optimal UAV Deployment for Delay-Bounded Data Collection in IoT Networks.''
In the IEEE International Conference on Computer Communications (INFOCOM 2024), Vancouver, Canada, 2024.
郭庭佑, 2022/09 - 2024/03. Algorithm Engineer @ TSMC
MS Research Work - ``On Min-Max Graph Balancing with Strict Negative Correlation Constraints.''
In proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), Kyoto, Japan, 2023.
Undergraduate students
林栢瑋、陳冠傑、簡駿騏、吳庭安、張皓嵅、吳柏橙、

Activity & Excursion

2024-06-13 期末聚餐 & 導生聚	2024-02-26 飛鳯山健行
2024-01-09 期末聚餐	2023-09-10 峨眉湖踏青	2023-09-06 攀岩體驗

Alumni

105 - 蕭家堯, co-advised with Academician D.T. Lee.
- Joint work - Tight Approximation for Partial Vertex Cover with Hard Capacities, Published in ISAAC'2017 & TCS.
- Master Thesis Awards from AACT in 2018, 獲演算法與計算理論學會 2017 & 2018 最佳碩士論文獎
106 - 洪恩平 (Eunpyeong Hong), co-advised with Academician D.T. Lee.
- Joint work - Approximation Algorithm for Vertex Cover with Multiple Covering Constraints, Published in ISAAC'2018 & Algorithmica.
- Master Thesis Awards from AACT in 2019, 獲演算法與計算理論學會 2018 & 2019 最佳碩士論文獎
108 (@CCU) - 陳竣煜、陳柏瑄
- Joint work produced - Optimal Construction for Time-Convex Hull with Two Orthogonal Highways in the L1-metric, CMCT 2021.
- MS Thesis (陳竣煜) - Optimal construction for time-convex hull with two orthogonal highways in the L1-metric
- MS Thesis (陳柏瑄) - Optimal construction for time-convex hull with two orthogonal highways and inifite speed in the L2-metric
108 (@CCU) - 蔡松穎、陳均豐
- Joint work produced - Domjudge_edu, [docs]
- MS Thesis (陳均豐) - 線上編譯環境與程式練習平台功能之整合 - 以 DomJudge 為基準
- MS Thesis (蔡松穎) - 打造適合用於教學環境的程式練習平台 - 以 DomJudge 為基準
109 (@CCU) - 葉修輔, MS Thesis - The 2-center Problem in Maximal Outerplanar Graph, CMCT 2022.
109 (@CCU) - 陳孟筠, MS Thesis - A literature survey on paired-domination problem in perfect graphs, 2023.